//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#include <gtest/gtest.h>

#include "hydra/lists/FineGrainedLockList.h"
#include "hydra/lists/OptimisticLockList.h"
#include "hydra/lists/LazyLockList.h"
#include "hydra/lists/LockFreeList.h"

using namespace Hydra;

class FineGrainedLockListTest : public ::testing::Test
{
protected:
	static const int NUM_THREADS = 4;
	static const int NUM_ITERATIONS = 5000;
	static const int NUM_SEARCH_ITERATIONS = 500;
	static void PushPop(FineGrainedLockListTest* test)
	{
		List& list = test->m_list;
		for( int i=0; i<NUM_ITERATIONS; ++i )
		{
			list.pushFront(i%4);
		}
		for( int i=0; i<NUM_ITERATIONS; ++i )
		{
			int x;
			if( list.popFront(x) )
				++test->m_counters[x];
		}
	}
	static void AddContainRemove(FineGrainedLockListTest* test, int threadId)
	{
		List& list = test->m_list;
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			list.pushFront(i);
		}
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			if( list.contains(i) )
				++test->m_counters[threadId];
		}
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			list.remove(i);
		}
	}
	typedef FineGrainedLockList<int> List;
	List m_list;
	Atomic<int> m_counters[NUM_THREADS];
};

TEST_F(FineGrainedLockListTest, Stuff)
{
	//
	//single thread functionality tests
	//
	int value;
	EXPECT_TRUE(m_list.isEmpty());
	EXPECT_TRUE(!m_list.front(value));
	m_list.pushFront(10);
	EXPECT_TRUE(!m_list.isEmpty());
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==10);
	m_list.pushFront(20);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==20);
	m_list.pushFront(30);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==30);
	m_list.pushFront(40);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==40);
	EXPECT_TRUE(m_list.contains(10));
	EXPECT_TRUE(m_list.contains(40));
	EXPECT_TRUE(!m_list.contains(50));
	EXPECT_TRUE(!m_list.remove(100));
	EXPECT_TRUE(m_list.remove(20));
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==40);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==30);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==10);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==10);
	EXPECT_TRUE(m_list.isEmpty());
	EXPECT_TRUE(!m_list.popFront(value));
	m_list.pushFront(50);
	m_list.pushFront(60);
	m_list.pushFront(70);
	m_list.pushFront(60);
	m_list.removeAll(60);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==70);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==50);
	EXPECT_TRUE(m_list.isEmpty());
	m_list.pushFront(100);
	m_list.pushFront(110);
	m_list.pushFront(120);
	EXPECT_TRUE(!m_list.isEmpty());
	m_list.clear();
	EXPECT_TRUE(m_list.isEmpty());

	//iterators
	{
		m_list.pushFront(10);
		m_list.pushFront(11);
		m_list.pushFront(12);
		m_list.pushFront(13);
		{
			List::Iterator iter(m_list);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
			EXPECT_TRUE(iter.next()==13);
			EXPECT_TRUE(iter.next()==12);
			EXPECT_TRUE(iter.peekNext()==11);
			EXPECT_TRUE(iter.next()==11);
			m_list.insert(iter, 100);
			EXPECT_TRUE(iter.next()==100);
			m_list.insert(iter, 200);
			EXPECT_TRUE(iter.peekNext()==200);
			m_list.remove(iter);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.next()==10);
			EXPECT_TRUE(!iter.hasNext());
			iter.toFront();
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
		}
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==13);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==12);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==11);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==100);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==10);
		m_list.clear();
	}

	//
	//multithread tests
	//
	Thread threads[NUM_THREADS];
	{
		for( int i=0; i<NUM_THREADS; ++i )
		{
			threads[i] = Thread(&PushPop, this);
			m_counters[i] = 0;
		}
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Start();
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Join();
		for( int i=0; i<NUM_THREADS; ++i )
			EXPECT_TRUE(m_counters[i]==NUM_ITERATIONS*NUM_THREADS/4);
		EXPECT_TRUE(m_list.isEmpty());
	}
	{
		for( int i=0; i<NUM_THREADS; ++i )
		{
			threads[i] = Thread(&AddContainRemove, this, i);
			m_counters[i] = 0;
		}
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Start();
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Join();
		for( int i=0; i<NUM_THREADS; ++i )
			EXPECT_TRUE(m_counters[i]==NUM_SEARCH_ITERATIONS);
		EXPECT_TRUE(m_list.isEmpty());
	}
}


template<typename List>
class ValidateLockListTest : public ::testing::Test
{
protected:
	static const int NUM_THREADS = 4;
	static const int NUM_ITERATIONS = 5000;
	static const int NUM_SEARCH_ITERATIONS = 500;
	static void PushPop(ValidateLockListTest* test)
	{
		List& list = test->m_list;
		for( int i=0; i<NUM_ITERATIONS; ++i )
		{
			list.pushFront(i%4);
		}
		for( int i=0; i<NUM_ITERATIONS; ++i )
		{
			int x;
			if( list.popFront(x) )
				++test->m_counters[x];
		}
	}
	static void AddContainRemove(ValidateLockListTest* test, int threadId)
	{
		List& list = test->m_list;
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			list.pushFront(i);
		}
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			if( list.contains(i) )
				++test->m_counters[threadId];
		}
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			list.remove(i);
		}
	}
	List m_list;
	Atomic<int> m_counters[NUM_THREADS];
};

typedef ::testing::Types<OptimisticLockList<int>, LazyLockList<int> > ValidateLockListTestTypes;
TYPED_TEST_CASE(ValidateLockListTest, ValidateLockListTestTypes);


TYPED_TEST(ValidateLockListTest, Stuff)
{
	//
	//single thread functionality tests
	//
	int value;
	EXPECT_TRUE(m_list.isEmpty());
	EXPECT_TRUE(!m_list.front(value));
	m_list.pushFront(10);
	EXPECT_TRUE(!m_list.isEmpty());
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==10);
	m_list.pushFront(20);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==20);
	m_list.pushFront(30);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==30);
	m_list.pushFront(40);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==40);
	EXPECT_TRUE(m_list.contains(10));
	EXPECT_TRUE(m_list.contains(40));
	EXPECT_TRUE(!m_list.contains(50));
	EXPECT_TRUE(!m_list.remove(100));
	EXPECT_TRUE(m_list.remove(20));
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==40);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==30);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==10);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==10);
	EXPECT_TRUE(m_list.isEmpty());
	EXPECT_TRUE(!m_list.popFront(value));
	m_list.pushFront(50);
	m_list.pushFront(60);
	m_list.pushFront(70);
	m_list.pushFront(60);
	m_list.removeAll(60);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==70);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==50);
	EXPECT_TRUE(m_list.isEmpty());
	m_list.pushFront(100);
	m_list.pushFront(110);
	m_list.pushFront(120);
	EXPECT_TRUE(!m_list.isEmpty());
	m_list.clear();
	EXPECT_TRUE(m_list.isEmpty());

	//iterators
	{
		m_list.pushFront(10);
		m_list.pushFront(11);
		m_list.pushFront(12);
		m_list.pushFront(13);
		{
			TypeParam::Iterator iter(m_list);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
			EXPECT_TRUE(iter.next()==13);
			EXPECT_TRUE(iter.next()==12);
			EXPECT_TRUE(iter.peekNext()==11);
			EXPECT_TRUE(iter.next()==11);
			EXPECT_TRUE(iter.lockAndValidate());
			EXPECT_TRUE(iter.isValidated());
			m_list.insert(iter, 100);
			EXPECT_TRUE(iter.isValidated());
			iter.unlock();
			EXPECT_TRUE(!iter.isValidated());
			EXPECT_TRUE(iter.next()==100);
			EXPECT_TRUE(iter.lockAndValidate());
			m_list.insertAndUnlock(iter, 200);
			EXPECT_TRUE(iter.peekNext()==200);
			EXPECT_TRUE(iter.lockAndValidate());
			m_list.removeAndUnlock(iter);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.next()==10);
			EXPECT_TRUE(!iter.hasNext());
			iter.toFront();
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
		}
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==13);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==12);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==11);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==100);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==10);
		m_list.clear();
	}

	//
	//multithread tests
	//
	Thread threads[NUM_THREADS];
	{
		for( int i=0; i<NUM_THREADS; ++i )
		{
			threads[i] = Thread(&PushPop, this);
			m_counters[i] = 0;
		}
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Start();
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Join();
		for( int i=0; i<NUM_THREADS; ++i )
			EXPECT_TRUE(m_counters[i]==NUM_ITERATIONS*NUM_THREADS/4);
		EXPECT_TRUE(m_list.isEmpty());
	}
	{
		for( int i=0; i<NUM_THREADS; ++i )
		{
			threads[i] = Thread(&AddContainRemove, this, i);
			m_counters[i] = 0;
		}
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Start();
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Join();
		for( int i=0; i<NUM_THREADS; ++i )
			EXPECT_TRUE(m_counters[i]==NUM_SEARCH_ITERATIONS);
		EXPECT_TRUE(m_list.isEmpty());
	}
}


class LockFreeListTest : public ::testing::Test
{
protected:
	static const int NUM_THREADS = 4;
	static const int NUM_ITERATIONS = 5000;
	static const int NUM_SEARCH_ITERATIONS = 500;
	static void PushPop(LockFreeListTest* test)
	{
		List& list = test->m_list;
		for( int i=0; i<NUM_ITERATIONS; ++i )
		{
			list.pushFront(i%4);
		}
		for( int i=0; i<NUM_ITERATIONS; ++i )
		{
			int x;
			if( list.popFront(x) )
				++test->m_counters[x];
		}
	}
	static void AddContainRemove(LockFreeListTest* test, int threadId)
	{
		List& list = test->m_list;
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			list.pushFront(i);
		}
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			if( list.contains(i) )
				++test->m_counters[threadId];
		}
		for( int i=0; i<NUM_SEARCH_ITERATIONS; ++i )
		{
			list.remove(i);
		}
	}
	typedef LockFreeList<int> List;
	List m_list;
	Atomic<int> m_counters[NUM_THREADS];
};

TEST_F(LockFreeListTest, Stuff)
{
	//
	//single thread functionality tests
	//
	int value;
	EXPECT_TRUE(m_list.isEmpty());
	EXPECT_TRUE(!m_list.front(value));
	m_list.pushFront(10);
	EXPECT_TRUE(!m_list.isEmpty());
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==10);
	m_list.pushFront(20);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==20);
	m_list.pushFront(30);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==30);
	m_list.pushFront(40);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==40);
	EXPECT_TRUE(m_list.contains(10));
	EXPECT_TRUE(m_list.contains(40));
	EXPECT_TRUE(!m_list.contains(50));
	EXPECT_TRUE(!m_list.remove(100));
	EXPECT_TRUE(m_list.remove(20));
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==40);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==30);
	EXPECT_TRUE(m_list.front(value));
	EXPECT_TRUE(value==10);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==10);
	EXPECT_TRUE(m_list.isEmpty());
	EXPECT_TRUE(!m_list.popFront(value));
	m_list.pushFront(50);
	m_list.pushFront(60);
	m_list.pushFront(70);
	m_list.pushFront(60);
	m_list.removeAll(60);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==70);
	EXPECT_TRUE(m_list.popFront(value));
	EXPECT_TRUE(value==50);
	EXPECT_TRUE(m_list.isEmpty());
	m_list.pushFront(100);
	m_list.pushFront(110);
	m_list.pushFront(120);
	EXPECT_TRUE(!m_list.isEmpty());
	m_list.clear();
	EXPECT_TRUE(m_list.isEmpty());

	//const iterator
	{
		m_list.pushFront(10);
		m_list.pushFront(11);
		m_list.pushFront(12);
		m_list.pushFront(13);
		{
			List::ConstIterator iter(m_list);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
			EXPECT_TRUE(iter.next()==13);
			EXPECT_TRUE(iter.next()==12);
			EXPECT_TRUE(iter.peekNext()==11);
			EXPECT_TRUE(iter.next()==11);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.next()==10);
			EXPECT_TRUE(!iter.hasNext());
			iter.toFront();
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
		}
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==13);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==12);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==11);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==10);
		m_list.clear();
	}

	//iterator
	{
		m_list.pushFront(10);
		m_list.pushFront(11);
		m_list.pushFront(12);
		m_list.pushFront(13);
		{
			List::Iterator iter(m_list);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
			EXPECT_TRUE(iter.next(value));
			EXPECT_TRUE(value==13);
			EXPECT_TRUE(iter.next(value));
			EXPECT_TRUE(value==12);
			EXPECT_TRUE(iter.peekNext()==11);
			EXPECT_TRUE(iter.next(value));
			EXPECT_TRUE(value==11);
			m_list.insert(iter, 100);
			EXPECT_TRUE(iter.next(value));
			EXPECT_TRUE(value==100);
			m_list.insert(iter, 200);
			EXPECT_TRUE(iter.peekNext()==200);
			bool isReset;
			EXPECT_TRUE(m_list.remove(iter, isReset));
			EXPECT_TRUE(!isReset);
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.next(value));
			EXPECT_TRUE(value==10);
			EXPECT_TRUE(!iter.hasNext());
			iter.toFront();
			EXPECT_TRUE(iter.hasNext());
			EXPECT_TRUE(iter.peekNext()==13);
		}
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==13);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==12);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==11);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==100);
		EXPECT_TRUE(m_list.popFront(value));
		EXPECT_TRUE(value==10);
		m_list.clear();
	}

	//
	//multithread tests
	//
	Thread threads[NUM_THREADS];
	{
		for( int i=0; i<NUM_THREADS; ++i )
		{
			threads[i] = Thread(&PushPop, this);
			m_counters[i] = 0;
		}
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Start();
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Join();
		for( int i=0; i<NUM_THREADS; ++i )
			EXPECT_TRUE(m_counters[i]==NUM_ITERATIONS*NUM_THREADS/4);
		EXPECT_TRUE(m_list.isEmpty());
	}
	{
		for( int i=0; i<NUM_THREADS; ++i )
		{
			threads[i] = Thread(&AddContainRemove, this, i);
			m_counters[i] = 0;
		}
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Start();
		for( int i=0; i<NUM_THREADS; ++i )
			threads[i].Join();
		for( int i=0; i<NUM_THREADS; ++i )
			EXPECT_TRUE(m_counters[i]==NUM_SEARCH_ITERATIONS);
		EXPECT_TRUE(m_list.isEmpty());
	}
}

